Projet ISOC 731

Forray Gabriel & Cochard Antoine

Installations and imports

#pip install matplotlib

import networkx as nx
import matplotlib.pyplot as plt
import random
from typing import List  
from dataclasses import dataclass  

1 - Random graph

options = {
    "font_size": 10,
    "node_size": 300,
    "node_color": "white",
    "edgecolors": "black",
    "linewidths": 1,
    "width": 1,
}

n = 100
p = 0.1

x = []
y = []

Gs = []

def generatGraph(p, ax):
    G = nx.fast_gnp_random_graph(100,p)
    Gs.append(G)
    nx.draw_networkx(G, **options, ax = ax)
    largest = len(sorted(nx.connected_components(G), key=len, reverse=True)[0])
    ax.set_title("Probability : " + str(p) + "\nSize of the largest connected component " + str(largest))
    x.append(p)
    y.append(largest)

fig, axs = plt.subplots(20,5,figsize=(40,250))



for i in range(100):
    generatGraph(i/100, axs[i//5, i%5])

plt.plot(x,y)
fig = plt.gcf()
fig.set_size_inches(20, 5)

On remarque que très vite, à partir de 5% ou 6% de probabilitée, tous les noeuds sont connectés entre eux.

def plot_degree_dist(G, ax, p):
    degrees = [G.degree(n) for n in G.nodes()]
    ax.set(xlim=(0, 100), ylim=(0, 40))
    ax.hist(degrees, bins=20)
    ax.set_title("Probability : " + str(p))

fig, axs = plt.subplots(10,10,figsize=(40,40))

i=0
for G in Gs:
    plot_degree_dist(G, axs[i//10, i%10], i/100)
    i += 1

On peut remarquer grâce à ces graphiques que le nombre moyen de voisins augmente quand la probabilité augmente. Il suffit de voir la "masse" bleu se déplacer doucement vers la droite au fur et à mesure que l'on augmente la probabilité que chaque noeud a de se relier aux autres. Logiquement donc, quand un noeud a peu de chances de créer des liens, le nombre moyen est faible voir nul pour la probabilité égale à 0. A la fin la probabilité approchant 1, le nombre de liaisons approche le nombre de noeuds total.

2 - Simple graph formation game

Without interferences

@dataclass
class Node(object):   
    ID: int   
    Value: int  
    Timing: float

def findNode(list, id):
    for n in list:
        if n.ID == id:
            return n   

def simple_game_without_interference(): 
    G = nx.Graph()

    Nodes = []

    n = 10

    # We create n nodes, each one has an id, a value initialized to 0 and a random timing value
    # Then we add them to the graph
    for i in range(n):
        node = Node(i, 0, random.random())
        Nodes.append(node)
        G.add_node(i, data = Node)

    # We sort the nodes by the timing value to determine the order in which the nodes will play
    Nodes = sorted(Nodes, key=lambda x: x.Timing)

    print("First Node : ", Nodes[0])

    # For each node
    for nodePlaying in Nodes:
        # We take the node by timing order
        
        # We make a list of nodes to which the playing node can connect (every node except him)
        index = Nodes.index(nodePlaying)
        selectableNodes = Nodes[:index]+ Nodes[index+1:]

        # We search for the maximum value in any nodes
        maxValue = max(selectableNodes, key = lambda node:node.Value).Value

        # If the max value is 0, there are no connections
        if maxValue == 0:
            # We get a random node
            nodeRandom = random.choice(selectableNodes)

            print("First random Node : ", nodeRandom)

            # We make the connection between the randomly selected node and the one with the lowest timing and set their values to 1
            G.add_edge(nodePlaying.ID, nodeRandom.ID)
            nodePlaying.Value = 1
            nodeRandom.Value = 1
        
        else:
            # We make a list of nodes that have the maximum value
            listMaxNodes = []
            for n in selectableNodes:
                if n.Value == maxValue:
                    listMaxNodes.append(n)
            
            # We select a random node between them
            nodeToConnect = random.choice(listMaxNodes)

            # If the nodes are not already connected, we connect them and increase their values
            if G.has_edge(nodePlaying.ID,nodeToConnect.ID) == False :

                G.add_edge(nodePlaying.ID, nodeToConnect.ID)
                
                if G.degree(nodePlaying.ID) == 1:
                    nodePlaying.Value = 1
                
                if G.degree(nodeToConnect.ID) == 1:
                    nodeToConnect.Value = 1

                if G.degree(nodePlaying.ID) > 1:
                    neighbors = G[nodePlaying.ID]
                    nodePlaying.Value = 0
                    for neighbor in neighbors:
                        nodePlaying.Value += findNode(Nodes, neighbor).Value
                
                if G.degree(nodeToConnect.ID) > 1:
                    neighbors = G[nodeToConnect.ID]
                    nodeToConnect.Value = 0
                    for neighbor in neighbors:
                        nodeToConnect.Value += findNode(Nodes, neighbor).Value



    nx.draw_networkx(G)

simple_game_without_interference()

First Node :  Node(ID=1, Value=0, Timing=0.2710702662465114)
First random Node :  Node(ID=9, Value=0, Timing=0.6095970356335733)

We can see that in every simulations, there is always one node in the center with all the other nodes connected to it. It is always either be the node with the lowest timing or the first randomnlly choosed Node.
It is like that because, when the second Node is choosing, they are the only two with a value of 1 instead of 0. The second Node will randomnly choose one of the two, increasing its value. Then this node will always be selected and increased at each step.

With inerference

def simple_game_wit_interference(ax):
    G = nx.Graph()

    Nodes = []

    n = 100

    # We create n nodes, each one has an id, a value initialized to 0 and a random timing value
    # Then we add them to the graph
    for i in range(n):
        node = Node(i, 0, random.random())
        Nodes.append(node)
        G.add_node(i)

    # We sort the nodes by the timing value to determine the order in which the nodes will play
    Nodes = sorted(Nodes, key=lambda x: x.Timing)

    first = "First Node : " +  str(Nodes[0].ID)

    # For each node
    for nodePlaying in Nodes:
        # We take the node by timing order
        
        # We make a list of nodes to which the playing node can connect (every node except him)
        index = Nodes.index(nodePlaying)
        selectableNodes = Nodes[:index]+ Nodes[index+1:]

        # We search for the maximum value in any nodes
        maxValue = max(selectableNodes, key = lambda node:node.Value).Value

        # If the max value is 0, there are no connections
        if maxValue == 0:
            # We get a random node
            nodeRandom = random.choice(selectableNodes)

            ax.set_title(first + "\nFirst random Node : " +  str(nodeRandom.ID))

            # We make the connection between the randomly selected node and the one with the lowest timing and set their values to 1
            G.add_edge(nodePlaying.ID, nodeRandom.ID)
            nodePlaying.Value = 1
            nodeRandom.Value = 1
        
        else:
            #Searching for the Node with the maximum vizible value
            nodeToConnect = None
            maxValue = 0
            for n in selectableNodes:
                #Wwhen looking for the value, modifying it with the interferences
                interferedValue = n.Value*random.randint(20,180)/100
                if interferedValue > maxValue:
                    maxValue = interferedValue
                    nodeToConnect = n

            # If the nodes are not already connected, we connect them and increase their values
            if G.has_edge(nodePlaying.ID,nodeToConnect.ID) == False :

                G.add_edge(nodePlaying.ID, nodeToConnect.ID)

                if G.degree(nodePlaying.ID) == 1:
                    nodePlaying.Value = 1
                
                if G.degree(nodeToConnect.ID) == 1:
                    nodeToConnect.Value = 1

                if G.degree(nodePlaying.ID) > 1:
                    neighbors = G[nodePlaying.ID]
                    nodePlaying.Value = 0
                    for neighbor in neighbors:
                        nodePlaying.Value += findNode(Nodes, neighbor).Value
                
                if G.degree(nodeToConnect.ID) > 1:
                    neighbors = G[nodeToConnect.ID]
                    nodeToConnect.Value = 0
                    for neighbor in neighbors:
                        nodeToConnect.Value += findNode(Nodes, neighbor).Value
                
    nx.draw_networkx(G, ax=ax)

fig, axs = plt.subplots(2,5,figsize=(40,10))

for i in range(10):
    simple_game_wit_interference(axs[i//5, i%5])